package com.wtgroup.demo.leetcode.q028_实现strStr;

import org.junit.Test;

/**
 * @author 60906
 * @date 2021/5/16 13:06
 */
public class Q028 {

    @Test
    public void foo1() {
        // String haystack = "babba";
        // String needle = "bbb";
        String haystack = "mississippi";
        String needle = "issip";
        int res = new Solution_KMP().strStr(haystack, needle);
        System.out.println(res);
    }


    class Solution_KMP {
        public int strStr(String haystack, String needle) {
            if (haystack.length() < needle.length()) {
                return -1;
            }
            if (needle.length()==0) {
                return 0;
            }

            int[] next = next(needle);

            int k = 0;
            int i = 0;
            while (i < needle.length() && k < haystack.length()) {
                if (needle.charAt(i) == haystack.charAt(k)) {
                    i++ ; k++;
                } else if(next[i] == -1){
                    k++; // 此时 i 已经是 0 了
                } else {
                    i = next[i];
                }
            }

            // needle 走完了=>匹配成功
            return i == needle.length() ? k - needle.length() : -1;
        }

        int[] next(String needle) {
            int n = needle.length();
            int[] next = new int[n];
            next[0] = -1;
            for (int i = 1; i < n; i++) {
                int x = next[i - 1];
                char preChar = needle.charAt(i - 1);
                while (x > -1 && needle.charAt(x) != preChar) {
                    x = next[x];
                }
                next[i] = x + 1; // -1 和 相等, 都是 +1
            }
            return next;
        }
    }


}
